package org.liaohailong.helloworld.study;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
 * Author: liaohailong
 * Time: 2021/5/8 17:42
 * Describe:
 */
public class MyStack {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            switch (c) {
                case '(':
                case '[':
                case '{':
                    stack.push(c);
                    break;
                case ')': {
                    if (stack.isEmpty()) return false;
                    Character pop = stack.pop();
                    if (pop != '(') return false;
                }
                break;
                case ']': {
                    if (stack.isEmpty()) return false;
                    Character pop = stack.pop();
                    if (pop != '[') return false;
                }
                break;
                case '}': {
                    if (stack.isEmpty()) return false;
                    Character pop = stack.pop();
                    if (pop != '{') return false;
                }
                break;
            }
        }
        return stack.isEmpty();
    }

    public int[] dailyTemperatures(int[] T) {
        Stack<Integer> stack = new Stack<>();
        int[] result = new int[T.length];
        for (int i = 0; i < T.length; i++) {
            int val = T[i];
            int index;
            int temp;
            // 栈为空，可能是第一个数下标入栈，也可能是前面的数都找到了观察天数
            if (stack.isEmpty()) {
                stack.push(i);
                continue;
            }
            while (!stack.isEmpty()) {
                index = stack.peek();
                temp = T[index];
                if (val > temp) {
                    result[index] = i - index;
                    stack.pop();
                } else {
                    break;
                }
            }
            stack.push(i);
        }

        return result;
    }


    // LC 逆波兰表达式求值
//    输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
//    输出：22
//    解释：
//    该算式转化为常见的中缀算术表达式为：
//            ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
//            = ((10 * (6 / (12 * -11))) + 17) + 5
//            = ((10 * (6 / -132)) + 17) + 5
//            = ((10 * 0) + 17) + 5
//            = (0 + 17) + 5
//            = 17 + 5
//            = 22
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            boolean op = isOp(token);
            if (op) {
                if (stack.size() < 2) {
                    stack.clear();
                    stack.push(0);
                } else {
                    Integer t2 = stack.pop();
                    Integer t1 = stack.pop();
                    int res = doOp(t1, t2, token);
                    stack.push(res);
                }
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

    private boolean isOp(String s) {
        if (s == null) return false;

        boolean ok = false;
        switch (s) {
            case "+":
            case "-":
            case "*":
            case "/":
                ok = true;
                break;
        }
        return ok;
    }

    private int doOp(int t1, int t2, String op) {
        int result = 0;
        switch (op) {
            case "+":
                result = t1 + t2;
                break;
            case "-":
                result = t1 - t2;
                break;
            case "*":
                result = t1 * t2;
                break;
            case "/":
                result = t1 / t2;
                break;
        }
        return result;
    }

    /**
     * 个位数的正整数的算数表达式转换为逆波兰表达式
     */
    public String[] parseEvalRPN(String str) {
        LinkedList<String> token = new LinkedList<>(); // 逆波兰表达式
        // 操作符号
        // 优先级：() 大于 */ 大于 +-
        Stack<String> stack = new Stack<>();
        // 数字直接计入token，符号判断，(直接入栈，
        // 遇到优先级大于栈顶的操作符号直接入栈，否则一致弹出栈顶，直到遇到比自己优先级小的操作符为止

        Map<String, Integer> priority = new HashMap<>();
        priority.put("(", 0);
        priority.put("*", 2);
        priority.put("/", 2);
        priority.put("+", 1);
        priority.put("-", 1);

        for (int i = 0; i < str.length(); i++) {
            String one = String.valueOf(str.charAt(i));

            // 数字直接加入结果
            if (isNumber(one)) {
                token.addLast(one);
            } else if (isSign(one)) {
                if (one.equals("(")) {
                    stack.push(one);
                } else if (one.equals(")")) {
                    while (!stack.peek().equals("(")) token.addLast(stack.pop());
                    stack.pop();// 把"("也弹出栈
                } else {
                    // 栈内没有操作符，直接输出
                    if (!stack.isEmpty()) {
                        int p1 = priority.get(one);
                        String top = stack.peek();
                        int p2 = priority.get(top);
                        if (p1 <= p2) {
                            // 本符号是+- 栈顶符号为*/
                            do {
                                String pop = stack.pop();
                                token.addLast(pop);
                                // 注意可能栈空的情况！！！
                                if (stack.isEmpty()) {
                                    break;
                                }
                                top = stack.peek();
                                p2 = priority.get(top);
                            } while (p1 <= p2);
                        }
                    }
                    stack.push(one);
                }
            }
        }

        // 栈内剩下的符号都是平级的，加入进来
        while (!stack.isEmpty()) {
            token.addLast(stack.pop());
        }

        return token.toArray(new String[]{});
    }

    private boolean isNumber(String s) {
        return !isSign(s);
    }

    private boolean isSign(String s) {
        boolean ok = false;
        switch (s) {
            case "+":
            case "-":
            case "*":
            case "/":
            case "(":
            case ")":
                ok = true;
                break;
        }
        return ok;
    }


    // LC 克隆图
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        return _cloneGraph(node, new HashMap<>());
    }

    private Node _cloneGraph(Node node, HashMap<Integer, Node> visitor) {
        Node record = visitor.get(node.val);
        if (record != null) {
            return record;
        }

        Node first = new Node(node.val);
        visitor.put(node.val, first);

        for (Node neighbor : node.neighbors) {
            first.neighbors.add(_cloneGraph(neighbor, visitor));
        }

        return first;
    }

    static final class Node {
        public int val;
        public List<Node> neighbors;

        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }
}
